package demo2String;

import org.junit.Test;

import java.util.Arrays;

/**
 * @ClassName $ {NAME}
 * @Description TODO  字符串去重排序
 * @Author shenxinyuan
 * @Date $ {DATE} $ {TIME}
 * @Version 1. 0
 **/

public class StringDeReordering {
    String str = "ae150wa5e";
    //思想：采用插入排序的方法，遇到重复的字符就不插入，否则就插入排序；时间复杂度O(n^3) 空间复杂度为O(n)
    public static String reOrdering(String str) {
        if (str.length() == 0 || str == null) {
            return null;
        }

        char[] res = new char[str.length()];
        int r=0;
        boolean label = true;
        res[0] = str.charAt(0);r++;

        for (int i = 1; i < str.length(); i++) {
            int j;
            char temp = str.charAt(i);
            int k;
            for (j = 0; j < r; j++) {

                if (res[j] == temp) {
                    label = false;
                    break;
                } else if (res[j] > temp) {
                    for (k = r - 1; k >= j; k--) {
                        swap(k + 1, k, res);
                    }
                    res[k+1] = temp;
                    break;
                }else if(j==r-1){
                    res[r] = temp;
                    break;
                }
            }
            if(label) {
                r++;
            }else {
                label = true;
            }
        }


        return new String(res).substring(0,r);
    }

    //优化方法
    //先排序，然后循环判断时都有重复字符，时间复杂度O(nLg(n)) 空间复杂度为O(n)
    public static String reOrderingOptimized(String str){
        char[] chars = str.toCharArray();
        char[] chs = new char[str.length()];
        int j =0;
        Arrays.sort(chars);

        for(int i =0;i<chars.length-1;i++){
            if(chars[i] != chars[i+1]){
                 chs[j++] = chars[i];
            }
        }
        return new String(chs).substring(0,j);
    }

    private static void swap(int i, int k, char[] res) {
        char t = res[i];
        res[i] = res[k];
        res[k] = t;
    }

    @Test
    public void test() {
        System.out.println("reOrdering(str) = " + reOrdering(str));
        System.out.println("reOrderingOptimized(str) = " + reOrderingOptimized(str));
    }
}
